class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

/**
 * 利用先序遍历和中序遍历的数组来创建二叉树
 */

public class Solution {
    private int index = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0) {
            return null;
        }
        return creatTree(preorder, inorder, 0, inorder.length - 1);
    }

    private TreeNode creatTree(int[] preorder, int[] inorder, int left, int right) {
        if(left > right) {
            return null;
        }
        for(int i = left; i <= right; i++) {
            if(preorder[index] == inorder[i]) {
                TreeNode root = new TreeNode(inorder[i]);
                index++;
                root.left = creatTree(preorder, inorder, left, i - 1);
                root.right = creatTree(preorder, inorder, i + 1, right);
                return root;
            }
        }
        return null;
    }
}